The invention relates to audio signal processing. In particular, the invention relates to the reduction of latency (i.e., time delay) in the digital encoding of audio information.
Various methods of data transmission and storage require mechanisms to detect (or detect and conceal) errors. In order to do so, data is often partitioned into portions, packets, or segments such that for a given segment, appropriate error detection or concealment information is generated. This information, typically a codeword or parity word, may be associated with the segment in a known position by an encoding or transmission process. A decoding or receiving system uses the codeword and its associated segment at least to detect the presence of errors, and, possibly to conceal errors. In the prior art, generation of the codeword requires prior knowledge of the entire segment. Consequently, the latency, that is, the time delay, between the receipt of information included in the segment and the segment""s transmission by an encoder or transmitter is a function of the position of the codeword in the transmitted segment. As explained below, latency resulting from codeword positioning in a data format is least when the codeword follows the other data; it is greatest when the codeword precedes the other data.
FIGS. 1-3 illustrate latency with respect to three examples of codeword positions. For simplicity of explanation of the effect of codeword position on latency in these and other figures throughout this document, the data applied to an encoder or transmitter along with any auxiliary data (including null or xe2x80x9cstuffingxe2x80x9d bits, if any) applied to or generated within the encoder or transmitter is shown already formatted into a block, frame or packet (in FIGS. 1-5, it is referred to as a xe2x80x9cmessage segmentxe2x80x9d). It will be understood that such a block, frame, packet or message segment is, in practice, built incrementally as incoming information is received and that doing so involves other latency considerations that form no part of the present invention.
In FIG. 1B, a received message segment 2 is shown. FIG. 1A shows the transmitted data format in which the message segment 2 is followed by a codeword 6. Ignoring all latency considerations other than those arising from the codeword location, the minimum latency between the onset of reception of the information that becomes message segment 2 and the earliest time at which transmission may begin is at least the sum of: (1) the time required to calculate the codeword, (2) the time required to insert the codeword into its location in the data format (which usually is very short), and (3) the time to transmit the codeword (times 1 and 2 are represented by an arrow 4 in FIG. 1A). It is possible to begin transmission well prior to generating the codeword. This codeword position is optimum from a codeword-position-caused latency standpoint because the onset of transmission does not require knowledge of the entire message. As explained further below, the present invention cannot improve latency when a codeword follows a message segment, such as in this example. Indeed, it will be seen that the invention strives to achieve the effect of such an optimum codeword position in systems in which the codeword position is not optimum (but which must remain in such a position because of compatibility or other requirements).
In order to provide a sense of the relative latencies in FIG. 1 (and in the following FIGS. 2-5) between the received information and the transmitted information, latency is indicated as the time lapse between the schematic rendition of the formatted received information (FIG. 1A and FIGS. 2A, 3A, 4A, 5A, 6A, and 7B) and the schematic rendition of the transmitted information (FIG. 1B, and FIGS. 2B, 3B, 4B, SB, 6B, and 7C, respectively).
FIGS. 2 and 3 show codeword positions for which the codeword-position-caused latency can be reduced by the present invention.
In FIG. 2A, a format is shown in which a received message segment is divided into two received message segments 8 and 10. FIG. 2 is idealized, schematic and not to scale (likewise, other figures herein are idealized, schematic and not to scale). For transmission, as shown in FIG. 2B, at least one error detection or concealment codeword 14 appropriate to the message segments 8 and 10 is generated and inserted in a codeword location in between message segments 8 and 10. Thus, relative to its optimum position after the message segment as shown in FIG. 1, the codeword position is toward the beginning of the message segment in the FIG. 2 format. The codeword position 14 is intended to show any codeword position between the beginning and end of a message segment. Again, ignoring all latency considerations other than those arising from the codeword location, the minimum latency between the onset of reception of the information that becomes message segment 8 and the earliest time at which transmission may begin is the sum of: (1) the time to receive the information that becomes the second part 10 of the message segment (FIGS. 2A and 2B assume that this is the same as the time period of segment 10 in the assembled data format and in the transmission), (2) the time required to calculate the codeword, (3) the time required to insert the codeword into its location in the data and format (the arrow 12 in FIG. 2 represents times 2 and 3), and (4) the time to transmit the codeword. It is possible to transmit the message portion that appears before the codeword before the codeword is generated, but the codeword or codewords in location 14 cannot be transmitted until the entire message segment is known, thus causing an additional latency at least as great as the time to receive the information that is transmitted as the second message segment 10. Thus, although it is possible to begin transmission prior to generating the codeword, transmission cannot begin as early as in the optimum end-of-message codeword position of FIG. 1.
In FIG. 3A, a received message segment 16 is shown. For transmission, as shown in FIG. 3B, an error detection or concealment codeword 20 appropriate to the message segment 16 is generated and inserted in a codeword location preceding the message segment. Once again, ignoring all latency considerations other than those arising from the codeword location, the minimum latency between the onset of reception of the information that becomes message segment 16 and the earliest time at which transmission may begin is the sum of: (1) the time to receive all the information that is transmitted as the message segment 16 (FIGS. 3A and 3B assume that this is the same as the time period of segment 16 in the assembled data format and in the transmission), (2) the time required to calculate the codeword, (3) the time required to insert the codeword into its location (an arrow 18 in FIG. 3 represents times 2 and 3), and (4) the time required to transmit the codeword. FIG. 3 illustrates the worst case codeword position from the standpoint of encoder latency.
Thus, in all of the three codeword locations illustrated in FIGS. 1-3, the latency is at least the sum of:
the time to calculate the codeword,
the time to insert the codeword into its location,
the time to transmit the codeword, and
the time to receive the information that is transmitted as the message segment (if any) or portion of the message segment (if any) that follows the codeword position in the transmission.
The requirement in the prior art that the codeword cannot be generated and transmitted until the entire message is known does not cause a latency problem if the codeword follows the entire message segment. The further the codeword position is from the end of the transmission, the greater the encoder latency. Thus, from an encoder latency reduction standpoint, it is desirable to locate the codeword at the entire end of the message segment or as close thereto as possible. When designing a new system, it may be possible to optimize the codeword location for low encoder latency. However, in the case of existing systems that must remain compatible with existing decoders and receivers, it is not practical to change the codeword location. Such new or existing systems may have a disadvantageous codeword location from the standpoint of encoder latency (i.e., a location other than following the message segment). The codeword location may have been chosen to satisfy other considerations and/or encoder latency may not have been a concern when the system was designed. For some applications, it would be desirable to improve the codeword-position-caused latency of such systems while preserving the backward compatibility of such systems. It should be noted that, in principle, encoder latency has no affect on latency in the decoderxe2x80x94improving decoder latency is not a part of the present invention.
The present invention seeks to reduce codeword-position-caused latency by avoiding the requirement for knowledge of the message prior to generating the error detecting or concealing codeword. A pseudo error detecting or concealing codeword is inserted in place of the normal error detecting or concealing codeword appropriate for the segment of information to which the error detecting or concealing codeword relates. However, in order to satisfy a conventional decoder or receiver, the pseudo error detecting or concealing information must match or be appropriate for the segment so that the decoder sees the codeword and message segment as valid or error free. This is accomplished by modifying or perturbing at least a portion of the segment to which the pseudo codeword relates. Such modification or perturbation may be accomplished in various ways depending on the nature of the error detecting or concealing information. When its nature permits, the segment preferably remains unchanged except in a portion or portions at or near the end of the segment in order to optimize the reduction of the codeword-position-caused latency. The pseudo error detecting or concealing information may be arbitrary (for example, it may be a random number or a pseudo-random number) or, optionally, it may convey information. In either case, the same information may be used as pseudo error detecting or concealing information in connection with all or selected segments, or, alternatively, the information constituting the pseudo error detecting or concealing information may change from segment to segment.
If possible, the segment should be changed in a way that does not degrade the quality of the message segment when decoded (e.g., in the case of audio, it is desirable that the change is not audibly perceptible). Some portions of the message may be more tolerant to modification than others, and some message formats may have ancillary, auxiliary, or null-bit data fields that can be changed without affecting user perceptible data. Nevertheless, in some cases, there may be a tradeoff between quality degradation and latency reduction.
In other words, one is dealing with two pieces of information, a message X and a corresponding error detection or concealment codeword Y. Generally, one cannot calculate Y until one has all of X, so if one needs to send Y before X, one has a minimum latency of the duration of X. The present invention sidesteps this problem by inserting Yxe2x80x2, a pseudo codeword instead of Y (in Y""s location in the data format) and starts sending X before one has all of X, but during X (preferably towards the end of X), one modifies X to Xxe2x80x2 so that when one calculates its codeword in the receiver or decoder, it just happens to be Yxe2x80x2.
Thus, in one aspect, the invention contemplates a method for reducing latency in the transmission of coded information relative to received information, wherein the coded information includes at least an encoded version of the received information or a modified form of an encoded version of the received information along with error detecting or concealing information appropriate for the coded information. The coded information optionally includes auxiliary information that may include null bits. The coded information is transmitted in a format in which the error detecting or concealing information has an assigned position that does not follow all of the received information or modified form of the received information. Pseudo error detecting or concealing information is generated. The coded information with the pseudo error detecting or concealing information located in the assigned position or positions is generated in which an encoded version of the received information is modified and/or auxiliary information is modified and inserted so that the pseudo error detecting or concealing information is appropriate for the coded information. The coded information is transmitted, whereby the transmission of coded information may begin before all of the received information is received. The pseudo error detecting or concealing information may be in the form of at least one error correcting or concealing codeword. The codeword may be in the form of at least one error detecting cyclic redundancy check (CRC) word.
FIGS. 4 and 5 show how the codeword-position-latency of the disadvantageous codeword locations of FIGS. 2 and 3, respectively, may be improved in accordance with the present invention.
In FIG. 4A, a received message segment is divided into two received message segments 8 and 10xe2x80x2. Unlike FIG. 2, in accordance with an embodiment of the invention, a modified data location 22 preferably toward the end of the second segment 10xe2x80x2 is provided in the transmitted format of FIG. 4B. Note that the second segment 10xe2x80x2 includes the modified data location 22 and the portion 10xe2x80x3 following the modified data location. The transmitted information, FIG. 4B, includes the first part of the message segment 8, followed by at least one pseudo codeword 14xe2x80x2 in a codeword position and the remaining part of the message segment 10xe2x80x2 that, in turn, includes modified data 24 in the modified data location. The modified data is chosen such that the pseudo codeword 14xe2x80x2 becomes appropriate for the entire transmission (i.e., it is the same as the codeword that would normally be generated for a transmission that includes the modified data 24). Consequently, ignoring all encoder latency considerations other than those arising from the modified data location, the minimum latency between the onset of reception of the information that becomes message segment 8 and the earliest time at which transmission may commence is the sum of: (1) the time to receive the information that is subsequently sent as the part 10xe2x80x3 of the message segment 10xe2x80x2 that follows the modified data 24, (FIGS. 4A and 4B assume that this is the same as the time period of part 10xe2x80x3 of message segment 10xe2x80x2 in the assembled data format of FIG. 4A and in the transmission format of FIG. 4B), (2) the time required to generate the modified data, (3) the time to insert the modified data into its location (an arrow 23 represents times 2 and 3 in FIG. 4), and (4) the time to transmit the modified data 24.
Comparing FIG. 4 to FIG. 2 shows that a substantial reduction in encoder latency is possible, namely as much as the difference between the time to receive the information that becomes the second message segment 10xe2x80x2 and the time to receive the information that becomes the message segment portion 10xe2x80x3 that follows the modified data in the transmission. If the modified data location is at the end of the part of message segment 10xe2x80x2 (i.e., there is no portion 10xe2x80x3 following the modified data), the latency is substantially the same as that resulting from the optimum codeword positioning at the end of the transmission (FIG. 1). However, in some data formats it may not be possible or desirable to locate the modified data at the end of the message segment.
In accordance with an embodiment of the invention, in FIG. 5A, unlike FIG. 3, a received message segment 16xe2x80x2 has a modified data location 26 toward the end of message segment 16xe2x80x2. As shown in FIG. 5B, the transmitted information includes a pseudo codeword 18xe2x80x2 followed by the message segment 16xe2x80x2 that includes modified data 28 in the modified data location. Note that the segment 16xe2x80x2 is all of the information following codeword 18xe2x80x2 including the modified data 28 in location 26 and the portion 16xe2x80x3 following the modified data. As in the case of the FIG. 4 embodiment, the modified data is chosen such that the pseudo codeword 18xe2x80x2 is appropriate for the entire transmission. Consequently, ignoring all latency considerations other than those arising from the modified data location, the minimum latency between the onset of reception of the information that becomes message segment 16xe2x80x2 and the earliest time at which transmission may commence is, as in the case of the FIG. 4 embodiment, the sum of: (1) the time to receive the information that is subsequently sent as the part 16xe2x80x3 of the message segment 16xe2x80x2 that follows the modified data location (FIGS. 4A and 4B assume that this is the same as the time period of part 16xe2x80x3 of the message segment 16xe2x80x2 in the assembled data format of FIG. 5A and in the transmission format of FIG. 5B), (2) the time required to generate the modified data, (3) the time to insert the modified data into its location (an arrow 27 represents times 2 and 3), and (4) the time to transmit the modified data.
Comparing FIG. 5 to FIG. 3 shows that a substantial reduction in encoder latency is possible, namely, as much as the difference between the time to receive the information that becomes message segment 16xe2x80x2 and the time to receive the information that becomes message segment 16xe2x80x3 that follows the modified data position 26. If the modified data location is at the end of the part of message segment 16xe2x80x2 (i.e., there is no portion 16xe2x80x3 following the modified data), the latency is equivalent to that resulting from the optimum codeword positioning at the end of the transmission (FIG. 1). As noted above, in some data formats it may not be possible or desirable to locate the modified data at the end of the message segment.